package classDesign;

import chapter02.MyUtil;

import java.io.*;
import java.util.Scanner;

/**
 * 给定n个整数组成的序列，现在要求将序列分割为m段，
 * 每段子序列中的数在原序列中连续排列。
 * 如何分割才能使这m段子序列的和的最大值达到最小？
 */

public class min_m {
    public static int minM(int a[], int n,int m) {
        int d[][] = new int[100][100];
        for(int i = 1; i <= n; i++) {
            d[i][1] = d[i-1][1] + a[i];//表示各子段的和
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 2; j <= m; j++){
                // 把i位整数划分成j段
                int min=Integer.MAX_VALUE;
                for (int k = j - 1; k < i; k++) {
                    int temp = Math.max(d[i][1] - d[k][1], d[k][j-1]);
                    if(temp < min) {
                        min  = temp; // 保存最小值
                    }
                }
                d[i][j] = min; //把所有k情况下的最小值赋值给d[i][j]。
            }
        }
        return d[n][m];//找到最优值
    }
    public static void main(String[] args) throws IOException {
        FileInputStream fileInputStream = new FileInputStream("src\\classDesign\\test\\sum5.in");
        Scanner scanner =new Scanner(fileInputStream);
        int n=scanner.nextInt();
        int m=scanner.nextInt();
        System.out.println(n);
        System.out.println(m);
        int[] a=new int[n+1];
        for (int i = 1; i <=n ; i++) {
            a[i]=scanner.nextInt();
        }
        MyUtil.printA(a,1);
        System.out.println(minM(a,n,m));
        File f=new File("src\\classDesign\\answer\\sum5.out");
        f.createNewFile();
        FileOutputStream fileOutputStream = new FileOutputStream(f);
        PrintStream printStream = new PrintStream(fileOutputStream);
        System.setOut(printStream);
        System.out.println(minM(a,n,m));

        printStream.close();
        fileOutputStream.close();
        fileInputStream.close();


    }
}
